package _01_排序;
/*
    快速排序的实现:
    ① 从序列中选择一个轴点元素（pivot） ✓ 假设每次选择 0 位置的元素为轴点元素
    ② 利用 pivot 将序列分割成 2 个子序列
    ✓ 将小于 pivot 的元素放在pivot前面（左侧）
    ✓ 将大于 pivot 的元素放在pivot后面（右侧）
    ✓ 等于pivot的元素放哪边都可以
    ③ 对子序列进行 ① ② 操作
    ✓ 直到不能再分割（子序列中只剩下1个元素）

    快速排序的本质:逐渐将每一个元素都转换成轴点元素
    时间复杂度:最好、平均O(nlogN),最坏(On^2),不稳定的排序
 */
public class QuickSort06<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    /**
     * 类似于前序遍历
     * 对 [begin,end) 范围内的元素进行快速排序
     * @param begin
     * @param end
     */
    private void sort(int begin,int end){
        if(end - begin < 2) return;

        int mid = pivotIndex(begin, end); //确定轴点元素并排序

        //对子序列在进行快速排序
        sort(begin,mid);
        sort(mid+1,end);
    }

    /**
     * 构造出 [begin,end)范围内的轴点元素，并进行排序
     * @param begin
     * @param end
     * @return 最终轴点元素所在的位置
     */
    private int pivotIndex(int begin,int end){
        //随机交换begin位置的元素，随机选择轴点元素，降低最坏时间复杂度
        //范围是 [begin,end)
        swap(begin,begin+(int)(Math.random()*(end - begin)));
        E pivot = array[begin]; //备份轴点元素
        end--; //取到最后一个元素
        while(begin<end){
            //使用两个循环来比较控制方向
            while(begin<end){ //先从右向左进行比较,如果大于轴点元素，就向前移动，否则将元素放到前面
                if(cmp(pivot,array[end])<0){
                    end--;
                }else{
                    array[begin++] = array[end];
                    break;
                }
            }

            while(begin<end){ //从左向右比较
                if(cmp(pivot,array[begin])>0){ //从左向右比较，如果小于轴点元素，就向后移动，否则将元素放到后面
                    begin++;
                }else{
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        //排完序后，此时begin = end就是轴点元素所在的位置,将轴点元素放入轴点的位置
        array[begin] = pivot;
        return begin;
    }
}
